Devices having a tracking capability (such as a hand-held scanner) require navigation functionality in order to maintain awareness of the device's present position on a piece of work. The surface texture of the work can provide a frame of reference for navigation. A known effective technique for enabling such navigation is to shine light at an angle on the work, and to process the resulting reflection, which will include the surface texture shadow of the work. This technique enables navigation using, for example, the fiber texture on the surface of a piece of paper from which an image is being scanned.
Part of such a navigation technique is correlation. In a series of frames representing portions of the image captured during motion across the image, correlation produces a numerical representation of "how much the current frame looks like the previous frame." Deriving this numerical representation is analogous to laying a photograph slide of a current image over a negative of a reference image, and then moving the slides around until the least amount of light gets through. The numerical representation sought in correlation corresponds actually to the amount of light that actually gets through at the nadir point and thus quantifies the "best fit" between the two images.
Correlation is typically performed in the digital domain in accordance with techniques described with reference to FIGS. 1A-1D. Reference image 101 on FIG. 1A comprises, for example, a 6.times.6 array of reference pixels R.sub.0 -R.sub.35. Each reference pixel R.sub.0 -R.sub.35 will be understood to be a digital value representative of the information seen by that pixel when the image was captured. Compare image 102 on FIG. 1A comprises a 6.times.6 array of compare pixels C.sub.0 -C.sub.35 clipped for the purposes of correlation to a 4.times.4 array 103. Referring now to FIG. 1B, compare array 103 is overlayed "dead center" on reference image 101, generating 16 calculations 104 as shown on FIG. 1B. In FIG. 1B, exemplary use is made in calculations 104 of the function (R.sub.X -C.sub.Y).sup.2, although other functions of R and C may be used in correlation, such as .vertline.R.sub.x -C.sub.y .vertline..
The aggregate sum of all 16 calculations 104 on FIG. 1B goes forward to form output value O.sub.4 on result surface 105 depicted on FIG. 1D. With further reference to FIG. 10, result surface is typically a 3.times.3 array of output values O.sub.0 -O.sub.8.
Turning now to FIG. 1C, array 103 is now overlaid, for example, on reference image 101 one reference pixel to the right of dead center. The aggregate sum of calculations 104 on FIG. 1B corresponding to this overlay yields output value 05 on result surface 105 on FIG. 1D. With further reference to FIG. 1C, array 103 is now overlaid, for example on reference image 101 one pixel diagonally up and to right of dead center. The aggregate sum of calculations 104 on FIG. 1B corresponding to this overlay yields output value O.sub.2 on result surface 105 on FIG. 1D.
The result of the foregoing process is that result surface 105 on FIG. 1D comprises a series of output values O.sub.0 -O.sub.8 each representative of correlation between array 103 and the corresponding patch of reference image 101 when array 103 is "moved around" reference image 101. The lowest value of O.sub.0 -O.sub.8 is the "best fit" and is the correlation value for reference image 101 and compare image 102.
Although exemplary use in FIGS. 1A-1D has been made of a 6.times.6 reference image 101 and compare image 102 (the compare image clipped to 4.times.4 to facilitate "movement" over reference image 101) in order to generate a 3.times.3 result surface, there is no limitation on these numbers to perform correlation according to the foregoing technique. Any size of reference image and compare image may be correlated, and the amount of "movement" enabled will dictate the size (and resolution) of the result surface.
Correlators of the current art using this technique typically store entire frames of digitized input pixel values in memory and then correlate the frames using an off-chip processor. Calculations are generally done serially for each output value over the result surface, calculations for the next output value not started until the previous output value has been determined. This results in a long latency from completion of the digitization of a frame until the result surface against the previous reference frame is calculated. There is also a high hardware overhead requiring at least two memory regions for the reference frame and the compare frame.
This type of batch processing causes slowdowns that could be remediated by more of a continuous and parallel processing of correlation calculations. It would also be advantageous to be able to perform correlation on-chip, which might become more feasible if the hardware requirements were optimized.
There is therefore a need in the art to perform correlation calculations in more of a "streaming" fashion, preferably on-chip.